package com.leetcode.partition6;

/**
 * @author `RKC`
 * @date 2021/10/29 15:47
 */
public class LC552学生出勤记录2 {

    private static final int MOD = 1000000007;

    public static int checkRecord(int n) {
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
        System.out.println(checkRecord(10101));
    }

    /**
     * dp的所有情况
     * dp[i][0][0]：今天截止0次缺席，今天截止0连续迟到。
     * dp[i][0][1]：今天截止0次缺席，今天截止1连续迟到。
     * dp[i][0][2]：今天截止0次缺席，今天截止2连续迟到。
     * dp[i][1][0]：今天截止1次缺席，今天截止0连续迟到。
     * dp[i][1][1]：今天截止1次缺席，今天截止1连续迟到。
     * dp[i][1][2]：今天截止1次缺席，今天截止2连续迟到。
     * 今天截止0次连续迟到：过去一定也是0次缺席，但可以有1、2次连续迟到 dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]
     * 今天截止1次缺席，0次连续迟到，分为两种情况：dp[i][1][0]=dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2]+dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]
     *      1）过去有1次缺席，但今天没有缺席，但过去可以有0、1、2次连续迟到 dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2]
     *      2）过去没有缺席，今天缺席了，但过去可以有0、1、2次连续迟到 dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2]
     * 今天截止0次缺席，1次连续迟到：过去0次缺席，0次迟到，今天迟到了：dp[i][0][1]=dp[i-1][0][0]
     * 今天截止0次缺席，2次连续迟到：过去0次缺席，昨天和今天都迟到了：dp[i][0][2]=dp[i-1][0][1]
     * 今天截止1次缺席，1次连续迟到：过去1次缺席，0次迟到，今天迟到了：dp[i][1][1]=dp[i-1][1][0]
     * 今天截止1次缺席，2次连续迟到：过去1次缺席，昨天和今天都迟到了：dp[i][1][2]=dp[i-1][1][1]
     */
    private static int dynamicProgramming(int n) {
        //dp[i][j][k]：第i天，在缺席了j次，以及连续迟到了k次的情况下，还可以拿到奖励的出席排列的数量。
        int[][][] dp = new int[n + 1][2][3];
        //没有任何出勤情况，A和L的数量必定是0，因此初始化只有1种情况
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i][0][0] = ((dp[i - 1][0][0] + dp[i - 1][0][1]) % MOD + dp[i - 1][0][2]) % MOD;
            dp[i][1][0] = (((dp[i - 1][1][0] + dp[i - 1][1][1]) % MOD + dp[i - 1][1][2]) % MOD + ((dp[i - 1][0][0] + dp[i - 1][0][1]) % MOD + dp[i - 1][0][2]) % MOD) % MOD;
            dp[i][0][1] = dp[i - 1][0][0];
            dp[i][0][2] = dp[i - 1][0][1];
            dp[i][1][1] = dp[i - 1][1][0];
            dp[i][1][2] = dp[i - 1][1][1];
        }
        //统计n天的所有情况返回
        int answer = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                answer = (answer + dp[n][j][k]) % MOD;
            }
        }
        return answer;
    }
}
